package dp;

public class LongestCommonSubseq {
	public enum Direction {
		UP, LEFT, UPLEFT
	}
	
	public static int lcsLength(String x, String y) {
		int m=x.length();
		int n=y.length();
		int c[][] = new int [m+1][n+1];
		Direction b[][] = new Direction[m+1][n+1];
		
		for (int i=0; i<m; i++) {
			c[i][0] = 0;
		}
		for (int j=0; j<n; j++) {
			c[0][j] = 0;
		}
		
		for (int i=1; i<=m; i++) {
			for (int j=1; j<=n; j++) {
				if (x.charAt(i-1) == y.charAt(j-1)) {
					c[i][j] = c[i-1][j-1]+1;
					b[i][j] = Direction.UPLEFT;
				}
				else if (c[i-1][j] >= c[i][j-1]) {
					c[i][j] = c[i-1][j];
					b[i][j] = Direction.UP;
				}
				else {
					c[i][j] = c[i][j-1];
					b[i][j] = Direction.LEFT;					
				}
			}
		}
		printLCS(b, x, m, n);
		return c[m][n];
	}
	
	public static void printLCS(Direction [][] b, String x, int i, int j) {
		if (i == 0 || j == 0) {
			return;
		}
		
		switch (b[i][j]) {
		case UPLEFT:
			printLCS(b, x, i-1, j-1);
			System.out.print(x.charAt(i));
			break;
		case UP:
			printLCS(b, x, i-1, j);
			break;
		case LEFT:
			printLCS(b, x, i, j-1);
			break;
		default:
			throw new RuntimeException("something is wrong");
		}
	}
	
	public static void main(String ...strings) {
		int lcsLength = lcsLength("ABCBDAB", "BDCABA");
		System.out.println(lcsLength);
	}
}
